<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
           最长重复子数组：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
           输入：
            A: [1,2,3,2,1]
            B: [3,2,1,4,7]
           输出：
            3
           解释：长度最长的公共子数组是 [3, 2, 1] 。

           分析：本质是找两个数组的交集数组 -> 交集数组的最大长度
        */
        /* 
            时间：O(n * m)
            空间：O(n * m)
        */
        var findLength = function(nums1, nums2) {
            let len1 = nums1.length;
            let len2 = nums2.length
            let dp = new Array(nums1.length + 1).fill(0).map(() => new Array(nums2.length + 1).fill(0))
            let result = 0
            // i和j均从1开始
            for (let i = 1; i <= len1; i++) {
                for (let j = 1; j <= len2; j++) {
                    // 注意，比较的是i - 1和j - 1是否相等
                    if (nums1[i - 1] === nums2[j - 1]) {
                        // 为什么是这个递推公式？dp[i][j]表示i-1和j-1的时候的公共数组的长度，dp[i][j]要在其基础上+1
                        dp[i][j] = dp[i - 1][j - 1] + 1
                        if (dp[i][j] > result) result = dp[i][j]
                    }
                }
            }
            return result
        };
        console.log(findLength([1,2,3,2,1], [3,2,1,4,7]));
        console.log(findLength([0,0,0,0,0], [0,0,0,0,0]));
    </script>
</body>

</html>